/*
 * Diseno de Algoritmos 2
 * Abril Julio 2011
 * David Subero
 * Daniel Bruzual
 * Job Shop resuelto a traves de ACO
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <sys/time.h>
#include <time.h>
#include "Lista.h"


#include "gopt.h"


#define MAX(a, b) ((a > b)? a: b)

typedef struct operacion {
	int id;
	int costo;
	int r; //tam del camino mas largo hasta ella desde el inicio
	int t; //tam del camino mas largo desde ella hasta el fin
	int maquina; //maquina a la que pertenece la operacion
	struct operacion *pj;
	struct operacion *sj;
	struct operacion *pm;
	struct operacion *sm;
} operacion;


typedef struct hormiga {
  operacion **tabu; //lista de nodos que ya fueron visitados
  operacion **candidatos; //nodos a los que la hormiga puede ir
  int *eft_maq; //costo de cada maquina en el recorrido
  int *eft_job; //costo de cada trabajo en el recorrido
  int makespan; //costo de la solucion parcial
  int makespan_ant;
  int pos_tabu;//pos libre en arreglo tabu
  int pos_cand;//pos libre en arreglo candidatos
} hormiga;


//numero de trabajos
int nro_t;

//numero de maquinas
int nro_m; 

//numero de operaciones totales 
int nro_op;

/* Mejor solucion encontrada hasta el momento representada como una
 * matriz que contiene por cada maquina, las operaciones en el 
 * orden que se realizan en ella
 */
operacion ***mejor_solucion;

operacion ***mejor_iter;
int mejor_iter_costo;

//Costo de la mejor solucion hasta el momento
int costo_mejor;

//arreglo de todas las hormigas
hormiga *colonia;

/* arreglo que contiene todas las operaciones
 * ordenadas por trabajo, y por precedencia
 * dentro de ese trabajo.
*/
operacion *operaciones;

//matriz de feromonas
float *feromonas;

/* Parametros de hormigas MinMax sugeridos por
 * Heinonen, J. and Pettersson, F
 */

//numero de hormigas
int num_ants = 40;

//peso de las feromonas
float alfa = 1;

//peso de la heuristica
float beta = 2;

//tasa de evaporacion
float ro = 0.007;

//Constante para cantidad de iteraciones
int C = 100;

//feromona inicial
float fero_ini = 0.151;
float feromona_max = 0.151;
float feromona_min = 0.0077;



/* Lee el archivo de una instancia e inicializa todas las estructuras
 * Parametros:
 *		archivo: nombre del archivo de la instancia
 * Valor de retorno:
 *		1 si el archivo no existe o si el formato del archivo no es valido
 *		-1 si no hay suficiente memoria disponible
 *		0 en otro caso
 */
int leer_instancia (char *archivo) {
  int i, j, maquina, costo;
  operacion *predecesor;
  FILE *fp;
  if ((fp = fopen(archivo, "r")) == NULL) {
    printf("ERROR: no se encontro el archivo \"%s\"\n",archivo);
    return 1;
  }
  
  if(!fscanf(fp, "%d %d\n", &nro_t, &nro_m)) {
    printf("ERROR: formato invalido\n");
    return 1;
  }
	
  //todas los trabajos tienen una operacion por maquina
  nro_op = nro_t * nro_m; 

  operaciones = (operacion *) calloc(nro_op,sizeof(operacion));
  if (operaciones == NULL) return -1;
  
  mejor_solucion = (operacion ***) calloc(nro_m,sizeof(operacion **));
  if (mejor_solucion == NULL) return -1;
  
  mejor_iter =  (operacion ***) calloc(nro_m,sizeof(operacion **));
  if (mejor_iter == NULL) return -1;

  feromonas = (float *) calloc((nro_op+1)*(nro_op), sizeof(float));
  if(feromonas == NULL) return -1;
  
  colonia = (hormiga *) calloc(num_ants, sizeof(hormiga));
  if(colonia == NULL) return -1;

  for (i=0; i<nro_m; i++) {
    mejor_solucion[i] = (operacion **) calloc(nro_t,sizeof(operacion *));
    if (mejor_solucion[i] == NULL) return -1;

    mejor_iter[i] = (operacion **) calloc(nro_t,sizeof(operacion *));
    if (mejor_iter[i] == NULL) return -1;

  }
  
  for (i=0; i<nro_t; i++) {
    predecesor = NULL;
    for (j=0; j<nro_m; j++) {
      if(!fscanf(fp, "%d %d\n", &maquina, &costo)) {
	printf("ERROR: formato invalido\n");
	return 1;
      }
      operaciones[i*nro_m + j].id = i*nro_m + j;
      operaciones[i*nro_m + j].costo = costo;
      operaciones[i*nro_m + j].maquina = maquina;
      operaciones[i*nro_m + j].pj = predecesor;
      operaciones[i*nro_m + j].pm = operaciones[i*nro_m + j].sm = NULL;
      if (j < nro_m - 1) {
	operaciones[i*nro_m + j].sj = operaciones + i*nro_m + j + 1;
      } else {
	operaciones[i*nro_m + j].sj = NULL;
      }
      
      predecesor = operaciones + i*nro_m + j;
    }
  }
  
  for(i=0; i<num_ants; i++){
    colonia[i].tabu = (operacion **) calloc(nro_op, sizeof(operacion*));
    if(colonia[i].tabu == NULL) return -1;
    colonia[i].candidatos = (operacion **) calloc(nro_t, sizeof(operacion*));
    if(colonia[i].candidatos == NULL) return -1;
    colonia[i].eft_maq = (int *) calloc(nro_m, sizeof(int));
    if(colonia[i].eft_maq == NULL) return -1;
    colonia[i].eft_job = (int *) calloc(nro_t, sizeof(int));
    if(colonia[i].eft_job == NULL) return -1;
  }
  return 0;
}


/*
 * Inicializa la estructura de las hormigas iniciales.
 * Todas las hormigas comienzan en la colonia.
 */
int init_colonia(){
  int i,j;

  for(i=0; i<num_ants; i++){
    //inicialmente, cada hormiga puede ir a los nodos que son
    //primera operacion de algun trabajo
    for(j=0; j<nro_t; j++){
      colonia[i].candidatos[j] = operaciones + j*nro_m;
      colonia[i].eft_job[j] = 0;
    }
    for(j=0; j<nro_m; j++){
      colonia[i].eft_maq[j] = 0;
    }
    colonia[i].makespan = 0;
    colonia[i].makespan_ant = 0;
    colonia[i].pos_tabu = 0;
    colonia[i].pos_cand = nro_t;
  }
  return 0;
}

/* 
 * Inicializa las feromonas entre cada par de nodos
 */
int init_feromonas(){
  int i,j, tam = (nro_op+1)*(nro_op);
  for(i=0; i<tam; i++){
    feromonas[i] = fero_ini;
  }
  return 0;
}

/* Dado que la matriz de feromona se maneja como una arreglo. 
 * pos_feromona hace la conversion de coordenadas matriciales
 * a lineales en ese arreglo. Es util en caso que se decida
 * representar la matriz dispersa de una forma mas eficiente
 */
int pos_feromona (int op1, int op2) {
  return op1*nro_op + op2;
}


/*
 * Guardar la solucion de una hormiga, expresado como la sucesion
 * de operaciones en el orden en que hizo el tour, en una matriz
 * de maquinas por operaciones. 
 * solucion[i][j], es la j-esima operacion realizada en la maquina
 * i.
 */
void guardar_solucion (hormiga *ant, operacion ***solucion) {
  int i, maquina, disponible_maq[nro_m];
  
  for (i=0; i<nro_m; i++) disponible_maq[i] = 0;
  
  for (i=0; i<ant->pos_tabu; i++) {
    maquina = ant->tabu[i]->maquina;
    solucion[maquina][disponible_maq[maquina]++] = ant->tabu[i];
  }
}

/* Imprime una solucion
 * Parametros:
 *		solucion: matriz que representa una solucion y contiene por cada maquina,
 *                las operaciones en el orden que se realizan en ella
 */
void imprimir_sol (operacion *** solucion) {
  int i, j;
  operacion *op;
  printf("Operaciones ordenadas en cada maquina segun se realizan.\n");
  printf("Solucion:\t(job, operation)\n");

  for (i=0; i<nro_m; i++) {
    printf("Maquina %d: ", i);
    for (j=0; j<nro_t; j++) {
        op = solucion[i][j];
        printf("(%d,%d)  ",op->id / nro_m, op->id % nro_m);
    }
    printf("\n");
  }
}

/* 
 * Lectura de parametros de entrada
 * alfa: peso de las feromonas en la decision
 * beta: peso de la heuristica en la decision
 * p (ro): tasa de evaporacion
 * i: numero de iteraciones
 * n: numero de hormigas
 * f: archivo con caso de prueba
 */
void read_args(int argc, const char ** argv, char ** filename){
  int  i;
  const char * input;


  void *options= gopt_sort( & argc, argv, gopt_start(
      gopt_option( 'a', GOPT_ARG, gopt_shorts( 'a'), gopt_longs("alfa. Peso a las feromonas.")),
      gopt_option( 'b', GOPT_ARG, gopt_shorts( 'b' ), gopt_longs("beta. Peso a la dictancia entre nodos.")),
      gopt_option( 'i', GOPT_ARG, gopt_shorts( 'i' ), gopt_longs("i. cantidad de iteraciones.")),
      gopt_option('f', GOPT_ARG, gopt_shorts('f'), gopt_longs("f. Caso de prueba.")),
      gopt_option('n', GOPT_ARG, gopt_shorts('n'), gopt_longs("n. Numero de hormigas.")),
      gopt_option( 'p', GOPT_ARG, gopt_shorts( 'p' ), gopt_longs("p. Tasa de evaporacion."))) );

   
   if( !gopt_arg( options, 'f', &input ) ){
     // Si no fue especificado un archivo 
     printf("Debe especificar un archivo de caso de prueba.\nUse el flag -f <archivo>\n");
     exit(-1);
   }  else {
     if((*filename = malloc(strlen(input)+1))==0){
       printf("Out of memory at initialization.\n");
       exit(1);
     } 
     for(i=0; ((*filename)[i]=input[i])!= 0; i++);
   }
   
   if( gopt_arg( options, 'a', &input ) ){
     //Si fue especificado alfa
     alfa = (float) atof(input);
     if(alfa<0){
       printf("Alfa debe ser mayor a 0.\n");
       exit(1);
     }
     printf("Alfa: %f\n", alfa);
   } else {
     printf("Alfa por defecto %f\n", alfa);
   }

   if( gopt_arg( options, 'b', &input ) ){
     //Si fue especificado beta
     beta = (float)atof(input);
     if(beta<0){
       printf("Beta debe ser mayor a 0.\n");
       exit(1);
     }
     printf("Beta: %f\n", beta);
   } else {
     printf("Beta por defecto: %f\n", beta);
   }

   if( gopt_arg( options, 'p', &input ) ){
     // Si fue especificado el ro
     ro = (float)atof(input);
     if(ro<0 || ro>1){
       printf("ro debe estar en [0,1].\n");
       exit(1);
     }
     printf("ro (p): %f\n", ro);
   } else {
     printf("ro (p) por defecto: %f\n", ro);
   }
   
   if( gopt_arg( options, 'n', &input ) ){
     // Si fue especificado el ro
     num_ants = atoi(input);
     if(num_ants<=0){
       printf("Una colonia de hormigas necesita tener al menos 1 hormiga.\n");
       exit(1);
     }
     printf("num hormigas: %d\n", num_ants);
   } else {
     printf("num hormigas por defecto: %d\n", num_ants);
   }
 

   if( gopt_arg( options, 'i', &input ) ){
     // Si fue especificada C
     C = (float)atof(input);
     printf("i: %d\n", C);
   } else {
     printf("i por defecto: %d\n", C);
   }
}

/*
 * Toma la decision de el siguiente nodo que debe visitar la hormiga h
 * en su tour por el grafo. Escoge ese nodo de manera aleatorea con
 * una distribucion de probabilidad que le da mayor peso a los nodos
 * que no aumentan el makespan.
 *
 * parametros:
 *        h    identificador de la hormiga
 */
void planificar_operacion (int h) {
  int i, op_actual, candidato, maqui, traba, empieza, z;
  hormiga *ant = colonia + h;
  float ferom;
  double max, aux=0, probabilidades[ant->pos_cand], retraso, q;
  
  /* {(pos_tabu==0) quiere decir que la hormiga no ha visitado nodos}
   * Por lo tanto se parte del nodo artificial de inicio, que tiene 
   * id=nro_op
   */ 
  if (ant->pos_tabu == 0) {
    op_actual = nro_op;
  } else {
    op_actual = ant->tabu[ant->pos_tabu-1]->id;
  }
  
  //Se calculan las probabilidades de escoger cada operacion candidata
  for (i=0; i<ant->pos_cand; i++) {
    if(ant->candidatos[i]->id % nro_m == 0){
      ferom = feromonas[pos_feromona(op_actual,ant->candidatos[i]->id)];
    } else {
      ferom = feromonas[pos_feromona(ant->candidatos[i]->id - 1,ant->candidatos[i]->id)];
    }
    
    //datos del candidato que esta siendo evaluado
    maqui = ant->candidatos[i]->maquina;
    traba = ant->candidatos[i]->id / nro_m;
    empieza = MAX(ant->eft_job[traba], ant->eft_maq[maqui])+operaciones[op_actual].costo; 

    //en cuanto aumenta el makespan si asigno esa operacion
    retraso = empieza - colonia[h].makespan;
    if(retraso <= 0 )retraso = 1; //hago esto para mantener consistencia con la formula
    
    probabilidades[i] = pow(ferom,alfa) * pow(1.0/retraso,beta);
    aux += probabilidades[i];
  }
  //calculo de probabilidad de cada candidato
  for (i=0; i<ant->pos_cand; i++) {
    probabilidades[i] /= aux;
  }
  
  //Se escoge uno de los candidatos tomando en cuenta sus probabilidades
  q = (double) rand() / RAND_MAX;
  aux = 0;
  for (i=0; i<ant->pos_cand; i++) {
    aux += probabilidades[i];
    if (q < aux) {
      candidato = i;
      break;
    }
  }

  //Se agrega el nodo escogido al tour de la hormiga
  ant->tabu[ant->pos_tabu++] = ant->candidatos[candidato];
  
  //Se actualizan las proximas operaciones candidatas a ser planificadas
  if (ant->candidatos[candidato]->sj) {
    ant->candidatos[candidato] = ant->candidatos[candidato]->sj;
  } else {
    ant->candidatos[candidato] = ant->candidatos[ant->pos_cand-1];
    ant->pos_cand--;
  }
  
  //Se lleva la cuenta de como afecta el candidato escogido los "earliest finishing time"
  //de su maquina y de su trabajo 
  if (ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina] > ant->eft_job[ant->tabu[ant->pos_tabu-1]->id / nro_m]) {
    ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina] += ant->tabu[ant->pos_tabu-1]->costo;
    ant->eft_job[ant->tabu[ant->pos_tabu-1]->id / nro_m] = ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina];
  } else {
    ant->eft_job[ant->tabu[ant->pos_tabu-1]->id / nro_m] += ant->tabu[ant->pos_tabu-1]->costo;
    ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina] = ant->eft_job[ant->tabu[ant->pos_tabu-1]->id / nro_m];
  }
  
  //Se actualiza el makespan
  if (ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina] > ant->makespan) {
    ant->makespan = ant->eft_maq[ant->tabu[ant->pos_tabu-1]->maquina];
  }  
}

/*
 * Pone un poco de feromonas en el ultimo arco recorrido por
 * la h-esima hormiga.
 */
void actualizar_feromona_local (int h) {
  
  hormiga *ant = colonia + h;
  int maq = ant->tabu[ant->pos_tabu-1]->maquina;
  int j, op1=-1, op2;

  //buscar la operacion anterior a la ultima asignada
  //pero que es procesada en la misma maquina
  for(j=ant->pos_tabu-2; j>= 0; j--){
    if(ant->tabu[j]->maquina == maq){
      op1 = ant->tabu[j]->id;
      break;
    }
  }
  if(op1 == -1) op1 = nro_op;
  op2 = ant->tabu[ant->pos_tabu-1]->id;
  feromonas[pos_feromona(op1,op2)] = (1-ro)*feromonas[pos_feromona(op1,op2)] + ro*fero_ini;
  
}

/*
 * Incrementa feromonas en todo el trayecto de la mejor hormiga de la
 * ultima iteracion.
 */
void actualizar_feromona_mejor(){
  int i, j, k;
  for(i=0; i<nro_m; i++){
    feromonas[pos_feromona(nro_op,mejor_iter[i][0]->id)] += 80/mejor_iter_costo;
    
    //revisar que no se pase del valor maximo permitido
    if(feromonas[pos_feromona(nro_op,mejor_iter[i][0]->id)] > feromona_max){
      feromonas[pos_feromona(nro_op,mejor_iter[i][0]->id)] = feromona_max;
    }

    for(j=0; j<nro_t-1; j++){
      feromonas[pos_feromona(mejor_iter[i][j]->id,
			      mejor_iter[i][j+1]->id)] += 80/mejor_iter_costo;

      //revisar que no se pase del valor maximo permitido
      if(feromonas[pos_feromona(mejor_iter[i][j]->id,
				mejor_iter[i][j+1]->id)] > feromona_max){
	feromonas[pos_feromona(mejor_iter[i][j]->id,
			       mejor_iter[i][j+1]->id)] = feromona_max;
      }
    }
  }
}


/*
 * Actualiza la feromonas de cada hormiga en todo su trayecto
 */
void actualizar_feromona_global (int iteracion) {
  int z, i, op1, op2, min = colonia[0].makespan;
  hormiga *ant = colonia;
  int planificacion[nro_m][nro_t];
  int dispo[nro_m];
  int maquina, identi, j, pos;

  for(z=0; z<num_ants; z++){
    ant = &colonia[z];
    for(i=0;i<nro_m;dispo[i++]=0);
    
    for(i=0; i<ant->pos_tabu; i++){
      maquina = ant->tabu[i]->maquina;
      identi = ant->tabu[i]->id;
    planificacion[maquina][dispo[maquina]++] = identi;
    }
    
    for(i=0; i<nro_m; i++){
      pos = pos_feromona(nro_op,planificacion[i][0]);
      feromonas[pos] = (1-ro)*feromonas[pos] + 1.0/ant->makespan;
      
    for(j=0; j<nro_t-1; j++){
      pos = pos_feromona(planificacion[i][j],planificacion[i][j+1]);
      feromonas[pos] = (1-ro)*feromonas[pos] + 1.0/ant->makespan;
    }
    }
    
  }
}
/* 
 * Lleva a cabo la evaporacion que ocurre en cada
 * iteracion.
 */
void evaporar(){
  int i;
  for(i=0; i<(nro_op+1)*nro_op; i++){
    feromonas[i] *= (1-ro);
    if(feromonas[i] < feromona_min){
      feromonas[i] = feromona_min;
    }
  }
}



/*
 * Esto se puede ignorar, fue usado para imprimir durante
 * la determinacion de valores de feromonas.
 */
void print_feromonas_mejor(){
  int i, j, k;
  for(i=0; i<nro_m; i++){
    for(j=0; j<nro_t-1; j++){
      printf("fero[%d][%d] = %f\n", mejor_solucion[i][j]->id,
	     mejor_solucion[i][j+1]->id,
	     feromonas[pos_feromona(mejor_solucion[i][j]->id,
				    mejor_solucion[i][j+1]->id)]);
    }
  }
}





void seed () {
    struct timeval t;
    gettimeofday(&t,NULL);
    srand(t.tv_sec * t.tv_usec);
}

void ant_colony(){
  int i, j, k, best_index, first_time =1;
  //inicializar feromonas
  init_feromonas();
  for (i=0; i<C; i++) {
    //inicializar poblacion
    init_colonia();

    //se construye una solucion por cada hormiga
    for (j=0; j<nro_op; j++) {
     
      for (k=0; k<num_ants; k++) {
        planificar_operacion(k);
      }
      /*      for (k=0; k<num_ants; k++) {
		actualizar_feromona_local(k);
		}*/
      
      //guardar la mejor hormiga de la iteracion
      mejor_iter_costo = 2147483647; //"infinito"
      for(k=0; k<num_ants; k++){
	if(colonia[k].makespan < mejor_iter_costo){
	  mejor_iter_costo = colonia[k].makespan;	  
	  guardar_solucion(&colonia[k], mejor_iter);
	  best_index = k;
	}
      }

    }
    //se actualiza la mejor solucion
    if(mejor_iter_costo < costo_mejor || first_time){
      guardar_solucion(&colonia[best_index], mejor_solucion);
      first_time = 0;
      costo_mejor = mejor_iter_costo;
    }

    evaporar();

    //    actualizar_feromona_global(i);
    //mejor de la iteracion
    actualizar_feromona_mejor();
   
  }

}

int main (int argc, const char **argv) {
  int error;
  char * filename;
  clock_t start, end;
  seed();
  start = clock();

  //lee los parametros de entrada y actualiza variables globales
  read_args(argc, argv, &filename);

  if (error = leer_instancia(filename)) {
    if (error == -1) printf("ERROR: la memoria disponible no es suficiente\n");
  	exit(1);
  }

  //alborotar el hormiguero
  ant_colony();
  
  end = clock();
  printf("Mejor costo: %d\n",costo_mejor);
  
  imprimir_sol(mejor_solucion);
  printf("duracion: %5.2f seg.\n",((double) (end - start)) / CLOCKS_PER_SEC );
  //  printf("%5.2f\n", ((double) (end - start)) / CLOCKS_PER_SEC );
  return 0;
}
